package algorthm.systemTraning.dynamicPlanning;
/**
 * @className: ViolentVersion
 * @Description:
 * @Author: wangyifei
 * @Date: 2024/3/20 9:12
 */
public class ViolentVersion {
    public static void main(String[] args) {
        int[] weight = {1, 2, 3, 9, 10};
        int[] value = {11, 21, 8, 9, 10};
        int bagWeight = 20;
        int maxValue = process(weight , value , 0 , bagWeight);
        System.out.println(maxValue);
//        System.out.println(process1(weight, value, bagWeight));

    }

    public static int process1(int[] weight , int[] value , int bagWeight){
        int[][] dp = new int[weight.length+1][bagWeight+1];
        int maxValue = 0;
        for(int j = 1 ; j <= bagWeight ; j++){
            for(int i = 0 ; i < weight.length ; i++){
                // 假如
                if(j < weight[i]){
                    dp[i+1][j] = dp[i][j];
                }else{
                    dp[i+1][j] = Math.max( dp[i][j] , dp[i][j - weight[i]] + value[i]);
                }
                if(dp[i+1][j] > maxValue){
                   maxValue = dp[i+1][j];
                }
            }
        }
        return maxValue ;
    }

    public static int process(int[] weight, int[] value , int startIdx ,int bagWeight) {
        if(startIdx == weight.length -1){
            return bagWeight >= weight[startIdx]? value[startIdx] : 0 ;
        }
        if(bagWeight < 0){
           return -1 ;
        }
        if(bagWeight == 0){
            return 0;
        }
        // 不要 startIdx 代表的物品
        int p1 = process(weight , value , startIdx + 1 , bagWeight);
        int p2 = process(weight , value , startIdx + 1 , bagWeight - weight[startIdx]);
        if(p2 < 0){
            return p1;
        }else{
           p2 = value[startIdx] + p2;
        }
        return Math.max(p1 , p2);
    }
}
